package code1_100.code50_60;

import java.util.Map;

/**
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 示例 1：
 *
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 *
 * 示例 2：
 *
 * 输入：nums = [1]
 * 输出：1
 *
 * 示例 3：
 *
 * 输入：nums = [0]
 * 输出：0
 *
 * 示例 4：
 *
 * 输入：nums = [-1]
 * 输出：-1
 *
 * 示例 5：
 *
 * 输入：nums = [-100000]
 * 输出：-100000
 *
 *
 1 <= nums.length <= 3 * 104
 -105 <= nums[i] <= 105

 *
 * 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解
 *
 *
 */
public class _53maxNumList {

    /**
     * 解题思路：
     * 1. 首先从第一个正数开始，因为前面的肯定是负增益
     * 2. 两个变量一个存放目前最优解，一个遍历数组是否继续累加
     * 3. 累加如果为负值，则此序列为负增益序列，可直接舍弃（跳转到下一个即可）
     * 4. 每次将ans和累加值比较，确保ans一直为两个中最大即可
     * @param nums
     * @return
     *
     * 执行用时：1 ms, 在所有 Java 提交中击败了95.20% 的用户
     * 内存消耗：38.4 MB, 在所有 Java 提交中击败了34.25% 的用户
     *
     */
    public static int maxSubArray(int[] nums){
        if(nums.length==1){
            return nums[0];
        }
        // 用来记录目前最大值
        int ans = 0;
        // 用来记录目前序列是否为最优序列
        int sum = 0;

        // 遍历数组,找第一个正数
        int i;
        // 如果全是负数，记录最大负数值，直接退出即可；
        int ansDe = nums[0];
        // 遍历第一遍，找第一个正数，如果全是负数，则返回最小的负数
        for (i = 0; i < nums.length; i++) {
            if (nums[i]>0){
                break;
            }else {
                ansDe = Math.max(ansDe,nums[i]);
            }
        }

        // 如果全是负数，直接退出
        if(i == nums.length){
            return ansDe;
        }

        //遍历寻找最大子序列
        int j;
        ans = nums[i];
        for (j = i;j<nums.length;j++){
            if(sum>0){
                sum += nums[j];
            }else {
                sum = nums[j];
            }
            ans = Math.max(sum, ans);
        }
        return ans;
    }


    /**
     * 上述加了很多判断，导致出内存消耗过大，这次看看不加判断的情况
     *
     * 发现这个结果还不如上述加了很多判断的
     * @param nums
     * @return
     *
     * 执行用时：1 ms, 在所有 Java 提交中击败了95.20% 的用户
     * 内存消耗：38.4 MB, 在所有 Java 提交中击败了35.39% 的用户
     *
     */
    public static int maxSubArray1(int[] nums){
        if (nums.length==1){
            return nums[0];
        }
        int ans = nums[0];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (sum > 0){
                sum += nums[i];
            }else {
                sum = nums[i];
            }
            ans = Math.max(sum,ans);
        }
        return ans;
    }


    /**
     * 上述加了很多判断，导致出内存消耗过大，这次看看不加判断的情况
     * 发现原因，上述调用Math库，增加了内存负担
     * @param nums
     * @return
     *
     * 执行用时：1 ms, 在所有 Java 提交中击败了95.20% 的用户
     * 内存消耗：38.4 MB, 在所有 Java 提交中击败了56.47% 的用户
     *
     */
    public static int maxSubArray2(int[] nums){
        if (nums.length==1){
            return nums[0];
        }
        int ans = nums[0];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (sum > 0){
                sum += nums[i];
            }else {
                sum = nums[i];
            }
            ans = sum>ans?sum:ans;
        }
        return ans;
    }


    public static void main(String[] args) {
        int[] nums = {-2,-1};
//        int[] nums = {5,4,-1,7,8};
//        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
//        int[] nums = {-3,1,-2,2};
        System.out.println(maxSubArray1(nums));
    }


}
